В последние годы большую популярность в работах по ИИ получили методы машинного обучения. Один из первых таких методов — подход к моделированию процессов обучения/развития на основе так называемых генетических алгоритмов.
Понятие о генетических алгоритмах
(Использован материал бывшего доступным в 2002 году сайта:
http://www.ai.tsi.lv/ru/index.htm, Борисов А.Н. Курс: Генетические алгоритмы, 2002)
Генетические алгоритмы (ГА) — это стохастические, эвристические оптимизационные методы, впервые предложенные Джоном Генри Холландом в книге «Адаптация в естественных и искусственных системах» (1975). Они основываются на идее эволюции с помощью естественного отбора, выдвинутой Дарвином.
ГА работают с совокупностью "особей" — популяцией, каждая из которых представляет возможное решение данной проблемы. Каждая особь оценивается мерой ее "приспособленности" согласно тому, насколько "хорошо" соответствующее ей решение задачи. В природе это эквивалентно оценке того, насколько эффективен организм при конкуренции за ресурсы. Наиболее приспособленные особи получают возможность "воспроизводить" потомство с помощью "перекрестного скрещивания" с другими особями популяции. Это приводит к появлению новых особей, которые сочетают в себе некоторые характеристики, наследуемые ими от родителей. Наименее приспособленные особи с меньшей вероятностью смогут воспроизвести потомков, так что те свойства, которыми они обладали, будут постепенно исчезать из популяции в процессе эволюции. Иногда происходят мутации, или спонтанные изменения в генах. 
Таким образом, из поколения в поколение, хорошие характеристики распространяются по всей популяции. Скрещивание наиболее приспособленных особей приводит к тому, что исследуются наиболее перспективные участки пространства поиска. В конечном итоге популяция будет сходиться к оптимальному решению задачи. Преимущество ГА состоит в том, что он находит приблизительные оптимальные решения за относительно короткое время.
ГА состоит из следующих компонентов: 1) Хромосома (Решение рассматриваемой проблемы. Состоит из генов); 2) Начальная популяция хромосом; 3) Набор операторов для генерации новых решений из предыдущей популяции; 4) Целевая функция для оценки приспособленности (fitness) решений. 
Чтобы применять ГА к задаче, сначала выбирается метод кодирования решений в виде строки. Фиксированная длина (l-бит) двоичной кодировки означает, что любая из 2l возможных бинарных строк представляет возможное решение задачи. Стандартные операторы для всех типов генетических алгоритмов это: селекция, скрещивание и мутация.
 Селекция
Оператор селекции (reproduction, selection) осуществляет отбор хромосом в соответствии со значениями их функции приспособленности. Существуют как минимум два популярных типа оператора селекции: рулетка и турнир. 
•	Метод рулетки (roulette-wheel selection) — отбирает особей с помощью n "запусков" рулетки. Колесо рулетки содержит по одному сектору для каждого члена популяции. Размер i-ого сектора пропорционален некоторой величине вычисляемой по формуле.
При таком отборе члены популяции с более высокой приспособленностью с большей вероятностью будут чаще выбираться, чем особи с низкой приспособленностью. 
•	Турнирный отбор (tournament selection) реализует n турниров, чтобы выбрать n особей. Каждый турнир построен на выборке k элементов из популяции, и выбора лучшей особи среди них. Наиболее распространен турнирный отбор с k=2. 
 Скрещивание
Оператор скрещивания (crossover) осуществляет обмен частями хромосом между двумя (может быть и больше) хромосомами в популяции. Может быть одноточечным или многоточечным. Одноточечный кроссовер работает следующим образом. Сначала, случайным образом выбирается одна из l-1 точек разрыва. Точка разрыва — участок между соседними битами в строке. Обе родительские структуры разрываются на два сегмента по этой точке. Затем, соответствующие сегменты различных родителей склеиваются и получаются два генотипа потомков.

      0       1       #       #      1

     0       1       #       1       0

     1       0       0       1       0

     1       0       0       #       1

Мутация
Мутация (mutation) — стохастическое изменение части хромосом. Каждый ген строки, которая подвергается мутации, с вероятностью Pmut (обычно очень маленькой) меняется на другой ген. 

      0       1       0       #       1

      0       1       1       #       1

Схема работы ГА
Работа ГА представляет собой итерационный процесс, который продолжается до тех пор, пока не выполнятся заданное число поколений или какой-либо иной критерий останова. На каждом поколении ГА реализуется отбор пропорционально приспособленности, кроссовер и мутация.

Схема работы простого ГА выглядит следующим образом:

Начальная
популяция

отбор

скрещивание

мутация

оценка
результата

Повторение цикла с новой популяцией

Задача решена.  Выход

Критерии остановки алгоритма:
•	нахождение глобального, либо субоптимального решения; 
•	исчерпание числа поколений, отпущенных на эволюцию; 
•	исчерпание времени, отпущенного на эволюцию. 

Генетические алгоритмы служат, главным образом, для поиска решений в очень больших, сложных пространствах поиска. Примеры реальных областей применения:
•	оптимизация запросов в базах данных;
•	задачи на графах (задача коммивояжера, раскраска);
•	задачи компоновки;
•	составление расписаний.
Замечание: Генетические алгоритмы и «метод проб и ошибок».

Искусственные нейронные сети
Исторические вехи:
1943 год — статья Маккалока и Питтса о математической модели нейронных сетей.
1949 год — книга Дональда Хебба «Организация поведения» с описанием процесса самообучения сетей.
1985 год — работы Джона Хопфилда по прменению сетей для решения реальных задач.
Искусственная нейронная сеть — математическая модель (и её программное или аппаратное воплощение), имеющая своим биологическим аналогом сети нервных клеток организма.
Элементы сети — соединённые и взаимодействующие между собой процессоры (искусственные нейроны). Каждый процессор имеет дело только с сигналами: получает от других процессоров, посылает другим процессорам. Большая сеть таких процессоров с управляемым взаимодействием способна решать довольно сложные задачи.

Бинарная классификация
Рассмотрим задачу бинарной (два класса) классификации. Пусть дана обучающая выборка, состоящая из N примеров: . Каждый пример — вектор вещественных чисел x(i) (вектор признаков) и метка соответствующего ему класса y(i). В случае бинарной классификации удобно считать, что (также именуемые положительным и отрицательным классами). Необходимо построить бинарный классификатор — функцию, которая для произвольного вектора x (не обязательно из обучающей выборки) возвращает метку соответствующего ему класса. Данная функция является аппроксимацией неизвестной нам истинной зависимости y от x. Она выбирается из некоторого семейства функций (множества функций одинакового вида, но отличающихся значениями ряда параметров) так, чтобы правильно классифицировать как можно большее число примеров из обучающей выборки. Часто на функцию накладывают также дополнительные ограничения, отражающие особенности предметной области и задачи. 

Замечание. Если истинная зависимость известна и ее можно записать в виде алгоритма, машинное обучение использовать не следует. В большинстве задач искусственного интеллекта это не так. Если появляется алгоритм, позволяющий решить задачу, ее ,как мы знаем, перестают относить к области искусственного интеллекта.

При построении классификатора методами машинного обучения необходимо определить:
1.	Гипотезу — семейство функций, среди которых будет происходить поиск наиболее подходящей.
2.	Оценочную функцию (cost / loss / objective function) — функцию, принимающую в качестве аргумента конкретный классификатор из семейства и возвращающую численную оценку его качества.
3.	Алгоритм обучения — алгоритм, позволяющий найти в семействе наиболее качественный с точки зрения оценочной функции классификатор (минимум оценочной функции). 

Логистическая регрессия (logistic regression)
Простейшим (вырожденным) случаем нейросети является нейросеть, состоящая из одного сигмоидального нейрона — логистическая регрессия. 
1.	Гипотеза: , где 
Примечание. Этот и другие рисунки взяты из работы: https://nlp.stanford.edu/courses/NAACL2013/.
Сначала нейрон вычисляет скалярное произведение вектора весов и входного вектора — другими словами, взвешенную сумму своих входов (если считать, что один из входов тождественно равен 1, то b можно рассматривать просто как вес одного из входов), затем к результату применяется сигмоида — функция, приводящее произвольное число к интервалу (0,1). Результат интерпретируется как вероятность принадлежности примера к положительному классу: если он больше ½ — пример классифицируется как положительный, иначе — как отрицательный. Веса являются параметрами и подбираются в процессе обучения.

Замечание. Вместо ½ может выбрано большее или меньшее значение в зависимости от того, какая из двух ошибок более опасна — отнесение положительного примера к отрицательному классу, или противоположная.

Замечание. Знак веса wi говорит о том, является ли признак xi свидетельством в пользу или против принадлежности примера к положительному классу, а величина веса — насколько сильным свидетельством это является.
2.	Оценочная функция: 

Каждое слагаемое определяет качество классификации одного из примеров обучающей выборки. Если пример относится к положительному классу (), то для минимизации оценочной функции возвращаемое классификатором значение должно быть как можно ближе к 1, если к отрицательному — то к 0. 

3.	Алгоритм обучения — градиентный спуск: 
Вначале веса инициализируются случайными числами (важно правильно выбрать распределение, из которого они генерируются). Затем в цикле вычисляется градиент оценочной функции в текущей точке и веса смещаются на небольшое расстояние в направлении, противоположном градиенту. Цикл завершается, когда веса перестают существенно изменяться (существуют также альтернативные критерии останова). 

Замечание. Градиент (вектор частных производных) в каждой точке указывает направление наискорейшего роста функции. Соответственно, противоположное направление — направление наискорейшего уменьшения функции. Если нужно как можно скорее спуститься на дно оврага, но мы находимся в лесу и за деревьями не видим этого дна, разумно все время идти в направлении наиболее резкого спуска — так и работает алгоритм градиентного спуска. Для подсчета градиента в каждой точке можно использовать метод конечных разностей, а можно аналитически найти частные производные и затем вычислять их значения в разных точках — второй способ гораздо быстрее в случае большой размерности вектора весов, именно он используется на практике. Гипотезы (в том числе нейронные сети) строят так, чтобы они были аналитически дифференцируемыми по своим параметрам функциями. Современные библиотеки работы с нейронными сетями выполняют аналитическое вычисление градиента автоматически.

Нейронная сеть прямого распространения с 1 скрытым слоем (feedforward neural network 1 hidden layer)
1.	Гипотеза: , где  , квадратные скобки обозначают объединение скаляров в вектор, либо векторов в матрицу.

Нейронную сеть прямого распространения с одним скрытым слоем размера m (из m нейронов) можно рассматривать как логистическую регрессию, на вход которой подаются выходы m логистических регрессий, в свою очередь получающих на вход вектор x — другими словами, это композиция / суперпозиция логистических регрессий. Градиент для такой модели можно эффективно вычислить с помощью правил дифференцирования сложной функции (chain rule).
2.	Если решается задача бинарной классификации, в простейшем случае можно использовать ту же оценочную функцию, что и для логистической регрессии. Выбор удачной оценочной функции для той или иной задачи — серьезная проблема, т.к. именно она в итоге определяет, чему учится сеть.
3.	В качестве алгоритм обучения также можно использовать градиентный спуск. Обычно используют его модификации [http://cs231n.github.io/neural-networks-3/#update].

Слой L2 называют скрытым, поскольку требуемые выходы нейронов этого слоя ai(2) в процессе обучения нами никак не определяются, в отличие от входного слоя L1 (который всегда совпадает с входным вектором x) и выходного слоя L3 (который обучается так, чтобы быть максимально близким к значению меток y). Это дает нейросети возможность самой учиться вычислять в скрытом слое такие функции от x, которые максимально полезны с точки зрения оценочной функции, т.е. позволяют максимально точно решать финальную задачу. 
Нейросеть с одним скрытым слоем является универсальным аппроксиматором: любую непрерывную функцию многих переменных можно аппроксимировать с любой наперед заданной точностью некоторой нейросетью с одним скрытым слоем (число нейронов в этом слое будут зависеть от функции и требуемой точности). С одной стороны это показывает, что нейросеть даже с одним скрытым слоем является достаточно мощным инструментом. С другой стороны из-за несовершенства обучающих выборок и алгоритмов обучения нет никаких гарантий, что полученная в результате обучения нейросеть будет аппроксимировать истинную зависимость y от x.

Нейронная сеть прямого распространения с несколькими скрытыми слоями

Хотя нейросеть даже с 1 скрытым слоем является универсальным аппроксиматором, во многих реальных задачах эффективнее оказываются многослойные нейросети. Причиной может служить то, что объекты и явления реального мира часто имеют иерархическую структуру, которая хорошо ложится на иерархическую структуру многослойной сети: 
буквы → слова → словосочетания → предложения → тексты
пиксели → уши, лапы, хвосты,... → животное.
Для определения того, какое животное представлено на изображении, полезно сначала обнаружить характерные для того или иного животного признаки: хвост, клюв, хобот. Для определения тональности отзыва о фильме — найти позитивно или негативно окрашенные слова. Имея такие нетривиальные промежуточные признаки, гораздо проще решить задачу, чем оперируя только буквами либо пикселями.

Важно, что нейроны в скрытых слоях в процессе обучения сами выбирают такие нетривиальные признаки входного изображения или текста, которые полезны для решения финальной задачи [http://yosinski.com/deepvis#toolbox]. Именно это считают одним из ключевых причин успеха многослойных нейронных сетей. Ранее, в эпоху преобладания линейных моделей машинного обучения (например, логистической регрессии), экспертам приходилось вручную придумывать такие признаки и описывать алгоритмы их обнаружения. Одно из направлений в области нейронных сетей — representation / feature learning изучает техники, позволяющие нейросетям находить полезные признаки во входных данных.

Типы нейронных сетей.
1.	Нейросети прямого распространения (feedforward NN, FFNN)
2.	Сверточные нейросети (convolutional NN, CNN)
3.	Рекуррентные нейросети (recurrent NN, RNN) [http://karpathy.github.io/2015/05/21/rnn-effectiveness/]
Современные нейронные сети часто комбинируют слои указанных типов в рамках одной сети. Также разрабатываются новые типы слоев [https://distill.pub/2016/augmented-rnns/].

Традиционная область применения сверточных нейросетей — анализ изображений, рекуррентных нейросетей — анализ текстов и вообще последовательностей.

Аналогично тому, как нейросети прямого распространения являются универсальным аппроксиматором, рекуррентные нейросети являются универсальным вычислителем: для любой машины Тьюринга можно построить эквивалентную рекуррентную нейросеть (вручную подобрав архитектуру и веса сети). К сожалению, из-за несовершенства алгоритмов обучения и обучающих выборок нет гарантий, что такая сеть будет построена алгоритмом обучения.

Примеры успешного применения нейросетей.
1.	Распознавание речи (speech recognition). В 2009 небольшая группа студентов под руководством Geoffrey Hinton используя 8-ми слойную нейросеть установили рекорд по качеству распознавания речи [http://www.cs.toronto.edu/~hinton/absps/NIPS09_DBN_phone_rec.pdf]. В 2012 году технология стала использоваться в Android, значительно улучшив качество распознавания речи.
2.	Классификация изображений. В 2009 для задачи классификации изображений был предложен датасет Imagenet [http://www.image-net.org/], содержащий более миллиона изображений, разбитых на 1000 классов. В 2012 нейросеть [Krizhevsky et. al. ImageNet Classification with Deep Convolutional Neural Networks] с большим отрывом по качеству классификации опередила все предшествующие подходы (сократила процент ошибок с 25% до 16%). Современные нейросети сократили процент ошибок до 4% и превзошли по качеству классификации людей [http://karpathy.github.io/2014/09/02/what-i-learned-from-competing-against-a-convnet-on-imagenet/].
3.	Игра в Го. В 2015 система AlphaGo победила действующего чемпиона по игре в Го со счетом 5:0 [https://deepmind.com/research/alphago/, https://storage.googleapis.com/deepmind-media/alphago/AlphaGoNaturePaper.pdf].    Го считается одной из наиболее сложных классических игр,  превосходящей  шахматы  по  размеру  пространства  перебора,  сложности оценки текущей позиции и выбора хода.
4.	Машинный перевод. [https://medium.com/@Synced/history-and-frontier-of-the-neural-machine-translation-dc981d25422d]
5.	Распознавание лиц. [https://medium.com/@ageitgey/machine-learning-is-fun-part-4-modern-face-recognition-with-deep-learning-c3cffc121d78]
6.	Генерация подписей к изображениям. [http://cs.stanford.edu/people/karpathy/deepimagesent/]

Причины успеха нейросетей 3-ей волны
1.	Появление достаточно мощных компьютеров. Использование современных видеокарт (GPU) ускоряют обучение нейросетей в десятки раз. Даже на современном сервере с 4-8 GPU обучение нейросети для машинного перевода или классификации изображений занимает несколько недель. Неудивительно, что раньше подобные эксперименты были просто невозможны.
2.	Появление больших датасетов. Например, Imagenet содержит миллионы изображений, WMT — несколько миллионов пар предложение → его перевод. Такие объемы необходимы, чтобы большие сложные нейросети не переобучались (не могли просто запомнить все примеры из обучающей выборки, а вынуждены были искать важные закономерности в данных). Большие сложные нейросети необходимы, чтобы улавливать сложные закономерности, необходимые для решения задач.
3.	Были разработаны более совершенные алгоритмы обучения нейронных сетей.